package com.algorithm.ch1.lzr.array;

/**
 * 有效的数独
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次
 * 数独部分空格内已填入了数字，空白格用 '.' 表示
 *
 * @author lzr
 * @date 2018/8/7
 */
public class IsValidSudoku {
    public static void main(String[] args) {
        char[][] board = {
                {'1', '.', '4', '.', '.', '.', '6', '3', '.'},
                {'.', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'5', '.', '.', '.', '.', '.', '.', '9', '.'},
                {'.', '.', '.', '1', '6', '.', '.', '.', '.'},
                {'4', '.', '3', '.', '.', '.', '.', '.', '1'},
                {'.', '.', '.', '7', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '5', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}};
        boolean validSudoku = isValidSudoku(board);
        System.out.println(validSudoku);
    }

    /**
     * 每一行/ 列
     * 每一个方格
     * char a = '.' 等价于 int a = 46  char a = '1' 等价于 int a = 49
     *
     * @param board 数独数组
     * @return 重复 true
     */
    private static boolean isValidSudoku(char[][] board) {
        //1.比较行列
        for (int i = 0; i < board.length; i++) {
            int[] temp1 = new int[9];
            int[] temp2 = new int[9];
            for (int j = 0; j < board.length; j++) {
                //比较行
                if (board[i][j] != '.') {
                    int valueX = board[i][j] - 49;
                    if (temp1[valueX] == 0) {
                        temp1[valueX] = 1;
                    } else {
                        return false;
                    }
                }
                //比较列
                if (board[j][i] != '.') {
                    int valueY = board[j][i] - 49;
                    if (temp2[valueY] == 0) {
                        temp2[valueY] = 1;
                    } else {
                        return false;
                    }
                }
            }
        }

        //2.判断9个 3X3 宫格内是否有重复
        for (int i = 0; i < board.length; i += 3) {
            for (int j = 0; j < board.length; j += 3) {
                int[] temp3 = new int[9];
                for (int k = i; k < i + 3; k++) {
                    if (board[k][j] != '.') {
                        int valueY = board[k][j] - 49;
                        if (temp3[valueY] == 0) {
                            temp3[valueY] = 1;
                        } else {
                            return false;
                        }
                    }
                    if (board[k][j + 1] != '.') {
                        int valueY = board[k][j + 1] - 49;
                        if (temp3[valueY] == 0) {
                            temp3[valueY] = 1;
                        } else {
                            return false;
                        }
                    }
                    if (board[k][j + 2] != '.') {
                        int valueY = board[k][j + 2] - 49;
                        if (temp3[valueY] == 0) {
                            temp3[valueY] = 1;
                        } else {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

}
